class Solution:
    def exist(self, board, word: str) -> bool:
        visited = dict()
        m = len(board)
        n = len(board[0])

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(i, j, word):
            if len(word) == 0:
                return True

            if board[i][j] != word[0]:
                return False
            
            res = False
            if board[i][j] == word[0]:
                visited[(i, j)] = True

                for d in directions:
                    ii, jj = i + d[0], j + d[1]
                    if ( 0 <= ii < m and 0 <= jj < n) and not visited.get((ii, jj), False):
                        sub = dfs(ii, jj, word[1:])
                        res = res or sub
            
                visited[(i, j)] = False

            return res
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    res = dfs(i, j, word)
                    if res == True:
                        return True
        return False

if __name__ == '__main__':
    s = Solution()
    board = [["A", "A"], ["B", "C"]]
    target = "AAB"
    res = s.exist(board, target)
    print(res)
